package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * 状态 dp[i][j] 定义如下：
 终止的时候，上面也分析了，输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][1]。
 * dp[i][j] 表示到下标为 i 的这一天，持股状态为 j 时，我们手上拥有的最大现金数。
 * <p>
 * 注意：限定持股状态为 j 是为了方便推导状态转移方程，这样的做法满足 无后效性。
 * <p>
 * 其中：
 * <p>
 * 第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）；
 * 第二维 j 表示下标为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）
 *  <p>
 *由于不限制交易次数，除了最后一天，每一天的状态可能不变化，也可能转移；
 * 写代码的时候，可以不用对最后一天单独处理，输出最后一天，状态为 0 的时候的值即可。
 * 起始的时候：
 * <p>
 * 如果什么都不做，dp[0][0] = 0；
 * <p>
 * 如果持有股票，当前拥有的现金数是当天股价的相反数，即 dp[0][1] = -prices[i]；
 * <p>
 * 终止的时候，上面也分析了，输出 dp[len - 1][0]，因为一定有 dp[len - 1][0] > dp[len - 1][1]。
 * <p>
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/9 14:41<br>
 */
public class 买卖股票的最佳时机II {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        //两个状态：手里没股票，手里有股票
        int dp0 = 0;
        int dp1 = Integer.MIN_VALUE;

        int preDp0 = dp0;
        int preDp1 = dp1;

        for (int price : prices) {
            //手里没股票
            dp0 = Math.max(preDp0, preDp1 + price);
            //手里有股票
            dp1 = Math.max(preDp1, preDp0 - price);

            preDp0 = dp0;
            preDp1 = dp1;
        }
        //返回没股票的时候
        return dp0;
    }
}
